package com.atguigu.leetcode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * TopK算法
 * @author xr-8
 * @date 2021-09-23
 * @time 22:10
 */
public class TopK {

    public static void main(String[] args) {
        int[] a = {9,2,12,4,18,63,7,8,9};
        int[] ints = topk_1(a, 4);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    //JDK自带函数版  1、利用集合的sort实现  2、利用队列实现
    public static int[] topk_1(int[] array, int k){
        Queue<Integer> q1 = new PriorityQueue<>((v1,v2)->v2-v1);
        for (int i = 0; i < array.length-1; i++){
           if(q1.size()<k){
               q1.offer(array[i]);
           }else{
               if(q1.peek()>array[i]){
                   q1.poll();
                   q1.offer(array[i]);
               }
           }
        }
        int[] result = new int[k];
        int index = 0;
        for (Integer integer : q1) {
            result[index++] = integer;
        }
        return result;
    }
}
